package test.maze;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

/**
 *  0 is path, 1 is wall, walk from left top (entrance) to right bottom (exit)
 *  
 * @author ginger
 *
 */
public class Maze {

	private int[][] maze = { //
	        { 0, 0, 0, 1 }, //
			{ 0, 1, 1, 1 }, //
			{ 1, 0, 0, 0 } //
	};

	int[][] newMaze;

	// wrap the maze with 1 to avoid border cases
	private int[][] createMaze() {
		newMaze = new int[maze.length + 2][maze[0].length + 2]; // [row], [column] !!
		for (int i = 0; i < maze.length + 2; i++) {
			for (int j = 0; j < maze[0].length + 2; j++) {
				if ((i == 0) || (j == 0) || (i == maze.length + 1) || (j == maze[0].length + 1)) {
					newMaze[i][j] = 1;
				} else {
					newMaze[i][j] = maze[i - 1][j - 1];
				}
			}
		}
		return newMaze;
	}

	private Stack<Position> stack = new Stack<Position>();
	
	private Set<Position> visitedPosition = new HashSet<Position>();

	private List<Position> nextMove(Position pos) {
		List<Position> poss = new ArrayList<Position>();

		// NE
		int x = pos.getX() + 1;
		int y = pos.getY() - 1;
		if (newMaze[y][x] == 0) {
			poss.add(new Position(x, y));
		}
		// East
		x = pos.getX() + 1;
		y = pos.getY();
		if (newMaze[y][x] == 0) {
			poss.add(new Position(x, y));
		}
		// SE
		y = pos.getY() + 1;
		if (newMaze[y][x] == 0) {
			poss.add(new Position(x, y));
		}
		// South
		x = pos.getX();
		if (newMaze[y][x] == 0) {
			poss.add(new Position(x, y));
		}
		// SW
		x = pos.getX() - 1;
		if (newMaze[y][x] == 0) {
			poss.add(new Position(x, y));
		}
		// West
		y = pos.getY();
		if (newMaze[y][x] == 0) {
			poss.add(new Position(x, y));
		}
		
		// can't go back !!
		for (Position p : visitedPosition) {
			poss.remove(p);
		}
		return poss;
	}

	protected boolean walk(Position pos) {
		visitedPosition.add(pos);
		stack.push(pos);
		
		// arrive
		if ((pos.getX() == maze[0].length) && (pos.getY() == maze.length)) {
			return true;
		}

		// dead end
		List<Position> nextPositions = nextMove(pos);
		if (nextPositions.isEmpty()) {
			stack.pop();
			return false;
		}
		
		
		for (Position next : nextPositions) {
			if (walk(next)) {
				return true;
			}
		}
		return false;
	}

	protected void printStack() {
		while (!stack.isEmpty()) {
			System.out.println(stack.pop());
		}
	}

	public static void main(String[] args) {
		Maze maze = new Maze();
		maze.createMaze();
		boolean succeed = maze.walk(new Position(1, 1));
		if (!succeed) {
			System.out.println("No path found");
		} else {
			maze.printStack();
		}
	}

}
